package hot100;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class d2_滑动窗口最大值 {
    public class MonotonicQueue<T extends Comparable<T>> {
        private final Deque<T> deque = new ArrayDeque<>();

        // 在尾部加入，保持单调递减
        public void push(T t) {
            while (!deque.isEmpty() && deque.peekLast().compareTo(t) < 0) {
                deque.removeLast();
            }
            deque.addLast(t);
        }

        // 从头部删除，只有等于队头才删（窗口滑出）
        public void pop(T t) {
            if (!deque.isEmpty() && deque.peekFirst().equals(t)) {
                deque.removeFirst();
            }
        }

        // 当前窗口最大值
        public T peek() {
            return deque.peekFirst();
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue<Integer> q = new MonotonicQueue<>();
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if(i >= k && nums[i - k] == q.peek()) {
                q.pop(nums[i - k]);
            }
            int num = nums[i];
            q.push(num);
            if (i >= k-1) {
                res[i - k + 1] = q.peek();
            }
        }
        return res;
    }
}
